
package main.old.new_2023.last.month_9;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description: todo 2651. 计算列车到站时间
 * 给你一个正整数 arrivalTime 表示列车正点到站的时间（单位：小时），另给你一个正整数 delayedTime 表示列车延误的小时数。
 * 返回列车实际到站的时间。
 * 注意，该问题中的时间采用 24 小时制。
 *
 * todo 207. 课程表
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0911 {

    //课程表 - 广度优先
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int count = numCourses;
        //广度优先
        //度为0的课程
        Queue<Integer> zeroCourse = new LinkedList<>();
        //保存课程的度数，下标为课程记号，值为度数
        int[] courseCount = new int[numCourses];
        //保存课程相互关联的关系，下标为课程记号，值为需要先完成的课程
        List<List<Integer>> courseRelation = new ArrayList<>();
        for (int i = 0;i<numCourses;i++){
            courseRelation.add(new ArrayList<>());
        }
        for (int[] coures:prerequisites){
            //度+1
            courseCount[coures[0]] = courseCount[coures[0]] + 1;
            //先读了 coures[1] 才能 读 coures[0]
            List<Integer> couseTemp = courseRelation.get(coures[1]);
            couseTemp.add(coures[0]);
            courseRelation.set(coures[1],couseTemp);
        }
        //筛选度为0的课程，加入队列，可以先读
        for (int i = 0;i<numCourses;i++){
            if (courseCount[i] == 0){
                zeroCourse.offer(i);

            }
        }
        while (!zeroCourse.isEmpty()){
            //吐出为0的课程，顺便把度 -1 ；
            Integer curese = zeroCourse.poll();
            count--;
            if (count<= 0){
                return true;
            }
            //以这门课为前置条件的课，度数可以-1
            List<Integer> tempCourse = courseRelation.get(curese);
            if (tempCourse.size()>0){
                tempCourse.forEach(course ->{
                    courseCount[course] = courseCount[course] -1;
                    if (courseCount[course]== 0){
                        zeroCourse.offer(course);
                    }
                });
            }
        }
        return false;
    }

    //课程表 - 深度优先
    public boolean canFinishShendu(int numCourses, int[][] prerequisites) {
        //保存课程相互关联的关系，下标为课程记号，值为需要先完成的课程
        List<List<Integer>> adjacency = new ArrayList<>();
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        //标记位，保存已经读过，无须再深度的课程, 0 -没有走过；
        int[] flags = new int[numCourses];
        for(int[] cp : prerequisites)
            adjacency.get(cp[1]).add(cp[0]);
        for(int i = 0; i < numCourses; i++)
            if(!dfs(adjacency, flags, i)) return false;
        return true;
    }
    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        //本节点启动的 DFS 访问过了，一旦遇到了也说明有环了
        if(flags[i] == 1) return false;
        //安全，直接返回
        if(flags[i] == -1) return true;
        flags[i] = 1;
        for(Integer j : adjacency.get(i))
            if(!dfs(adjacency, flags, j)) return false;
        flags[i] = -1;
        return true;
    }

    public static void main(String[] args) {
        int[][] temp= {{1,4},{2,4},{3,1},{3,2}};
        Solution0911 test = new Solution0911();
        test.canFinish(5,temp);
    }

    //计算列车到站时间
    public int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
        return (arrivalTime+delayedTime)%24;
    }



}
